Concentrators of various types are in common use in large switching systems like telephone exchanges. In a telephone exchange, typically a large number of input lines must be concentrated into a smaller number of trunks for transmission of the telephone signals. A concentrator consists of a crossbar made up of a number of controllable crosspoint switches that connect a given input to a given output.
For very large systems, the cost of the crossbar switch is quite high because of the large number of crosspoints implemented by electromechanical switches. For instance, for a crossbar having 100 inputs and 10 outputs, in order to assure full accessibility in a single stage crossbar by any input to each output, the crossbar would require 1000 crosspoint switches.
In order to reduce the cost of crossbar switches, a wide variety of concentrators has been developed that reduce the number of crosspoints required to assure an acceptable level of accessibility by a given input to an available output.
Representative systems of the prior art are described in the following sources:
M. W. Pinsker, "On the Complexity of a Concentrator", Proc. Internat. Teletraffic Conf., 7 (1973) 318/1-4. (Multistage rather than direct networks; rearrangeable rather than non-blocking operation; probabilistic construction--no reduction to practice.)
L. A. Bassalygo and M. S. Pinsker, "Complexity of an Optimum Nonblocking Switching Network without Reconnections", Prob. Info. Transm., 9 (1973) 64-66. (Connector rather than concentrator; multistage rather than direct network; probabilistic construction--no reduction to practice.)
G. A. Margulis, "Explicit Constructions of Concentrators", Prob. Info. Transm., 9 (1973) 325-332. (Rearrangeable rather than non-blocking operation.)
A. Feiner and W. S. Hayward, "No. 1 ESS Switching Network Plan", Bell Sys. Tech. J., (1964) 2193-2220. (Instance in practice of sparse crossbar; capacity in excess of accessibility not guaranteed.)
G. M. Masson, "Binomial Switching Networks for Concentration and Distribution", IEEE Trans. on Comm., 25 (1977) 873-883. (Rearrangeable rather than non-blocking operation.)
N. Pippenger, "Telephone Switching Network", Proc. of Symposia in Applied Mathematics, Vol. 26, (1982) 101-133.
U.S. Pat. Nos. 3,935,394, Bulfer, issued Jan. 27, 1976, entitled "Network Routing and Control Arrangement" and 4,245,214, Beirne, issued Jan. 13, 1981, entitled "Switching Matrix".
The cited literature consists of two main groups. The first concerns probabilistic operation of multiple stages of crossbars. These systems reduce the number of crosspoints by using multiple stages and a probabilistic control routine. The second class involves systems which are operated by rearranging busy connections when a new request for connection cannot be made with existing idle outputs.
The prior art systems cited above cannot provide a capacity for handling requests for connections that exceeds the accessibility of a given input to a number of outputs in a single stage crossbar without the rearrangement of existing connections.